package com.peng.tree.test_code.dp;

import com.peng.tree.Node;

/**
 * 是否是一颗满二叉树：
 * 满二叉树的节点个数 = 2^(树层数）-1
 */
public class Test08_IsFullTree {

    public static boolean isFullTree(Node head) {
        if (head == null) {
            return true;
        }
        TreeInfo info = process(head);
        return (1 << info.height) - 1 == info.size;

    }

    public static TreeInfo process(Node head) {
        if (head == null) {
            return new TreeInfo(0, 0);
        }
        TreeInfo leftInfo = process(head.left);
        TreeInfo rightInfo = process(head.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int size = leftInfo.size + rightInfo.size + 1;

        return new TreeInfo(height, size);

    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
//        node4.left = node8;
//        node4.right = node9;
        /*
                   1
             2              3
           4    5         6     7
         8   9

         */

        System.out.println(isFullTree(node));
    }

    static class TreeInfo {
        public int height;
        public int size;

        public TreeInfo(int height, int size) {
            this.height = height;
            this.size = size;
        }
    }
}
